package com.leetcode.offer;

import com.leetcode.entity.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zfl
 * @Classname GetKthFromEnd
 * @Description 链表中倒数第K个节点
 * @Date 2020/10/21 15:27
 */
public class GetKthFromEnd {

    /**
     * @param head
     * @param k
     * @return
     * 执行用时：1 ms, 在所有 Java 提交中击败了14.24%的用户
     * 内存消耗：36.7 MB, 在所有 Java 提交中击败了71.28%的用户
     */
    public static ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) {
            return null;
        }
        Map<Integer, ListNode> map = new HashMap<>();
        ListNode l1 = head;
        int count = 0;
        while (l1 != null) {
            count++;
            map.put(count, l1);
            l1 = l1.next;
        }
        return map.get(count - k + 1);
    }

    /**
     * @param head
     * @param k
     * @return
     * 双指针法
     */
    public static ListNode getKthFromEnd2(ListNode head, int k) {
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++)
            former = former.next;
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}
